1. Field of the Invention
The present invention relates to solving frequency, frequency distribution or sequence matching and comparison problems, and more particularly, to solving the comparison mapping and analysis of shapes, convex holes, areas and envelop, functions using two or more dimensional models represented as sequences of symbols and analyzed using a sequence attractor identity scheme.
2. Background Art
The following discussion of the background of the invention is merely provided to aid the reader in understanding the invention and is not admitted to describe or constitute prior art to the present invention.
The recognition of shapes is an important aspect of many fields and industries. For example, fields such as imagery analysis for mapping, identification of objects in images, guidance of vehicles and robots, recognition of parts in manufacturing, and recognition of scenes all require accurate detection and/or recognition of shapes. Further, recognition and detection of shapes is a key element in the digitization and categorization of shapes. For example, for certain artificial intelligence systems, it may be critical for the system to quickly determine whether a detected object is a cube, a circle, a face, or another category of objects. For other applications, it may be desirable to synthetically generate a shape, as may be the case in computer game graphics.
One concern with many existing techniques of shape recognition is that most are not affine independent. In this regard, the detected shape must be oriented and scaled exactly as the reference pattern to which it is compared in order for the system to recognize a match. If the detected shape is skewed, rotated, flipped, mirrored, distorted or translated, the system will most likely fail to detect a match.
One technique which provides some affine independence is a Fourier series representation. Encoding of shapes as sequences of directional vectors has been known and used as the discrete form of Fourier by, for example, Dougherty, Edward R., Mathematical Methods for Artificial Intelligence and Autonomous Systems, Englewood Cliffs, N. J.: Prentice Hall, 1988, pp. 370-89, which is hereby incorporated by reference. However, most computer implementations of Fourier require an extraordinarily large number of integration cycles. This limitation of Fourier presents a barrier for most real-time applications, since it limits the frequency at which the implementation may be applied. Attempts to obtain small increases in frequency can result in a large increase in the cost of the application. The problem may be exacerbated if an appropriate integrator is not available, making the matching an extremely difficult task. Further, even at its most successful, a Fourier series representation provides only an approximate match.
It would, therefore, be desirable to provide a method of accurately detecting, interpreting, recognizing, identifying and comparing shapes with greater affine independence without the need for large integration cycles.
The above background art is intended merely as a generic description of some of the challenges encountered by data processing hardware and software when solving waveform, signal attribute or sequence-matching problems, and not as any admission of prior art.
A method of characterizing an m-dimensional shape in an n-dimensional space according to an embodiment of the present invention includes configuring a device in at least one of hardware, firmware and software to characterize the m-dimensional shape. The configuring includes defining labels for a plurality of facial directions of a polytope in the n-dimensional space, the polytope being of k dimensions. The configuring further includes defining a unit vector for each of the facial directions, and defining a polytope tiling map for the n-dimensional space. The method includes tiling the m-dimensional shape with k-dimensional polytope within the n-dimensional space, and mapping a shape into a sequence of tile addresses. The device is configured to carry out an attractor process for mapping a source multiset to an attractor space, the attractor process being an iterative process which causes elements in the source multiset to converge on one of at least two different behaviors defined within the attractor space as a result of the iterative process, the configuring step including inputting a characterization of the source multiset to input to the device the number of distinct elements of the source multiset. The device is used, and the mapping of the sequence of tile addresses one or more coordinates of the attractor space is executed, each of the coordinates corresponding to a different behavior in the attractor space. In a preferred embodiment, the method may further include mapping the attractor space coordinates into a target space representation, the target space representation including at least the attractor space coordinates.